package org.laizili.solution.codinginterviews;

import org.laizili.structure.list.ListNode;

/**
 * <a href="https://leetcode-cn.com/problems/SLwz0R/">剑指 Offer II 021. 删除链表的倒数第 n 个结点</a>
 * <p>
 * tags: 链表; 快慢指针
 * </p>
 */
public class ProblemOffer021 {
    private static class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if (head == null) {
                return null;
            }
            ListNode slowCursor = head;
            ListNode slowCursorPrePos = null;
            ListNode fastCursor = head;
            int steps = 0;
            while (fastCursor != null) {
                steps++;
                if (steps > n) {
                    slowCursorPrePos = slowCursor;
                    slowCursor = slowCursor.next;
                }
                fastCursor = fastCursor.next;
            }
            if (steps >= n) {
                if (slowCursorPrePos == null)
                    head = head.next;
                else
                    slowCursorPrePos.next = slowCursor.next;
            }
            return head;
        }
    }
}
